The present invention relates in general to graphics data processing, and in particular to methods and systems for determining visibility of triangles and polygons.
In the field of computer graphics, complex images are generated from simple geometries such as triangles and polygons. A typical 3-dimensional (3-D) computer generated image may consist of millions of triangles and polygons. Each of these triangles and polygons, and mode information about the triangles and polygons, must be stored in memory and processed rapidly. Accordingly, developing techniques for efficiently storing graphics data in memory and rapidly processing that data are critical to improving the performance of computer graphics systems.
From any given viewpoint, not all triangles forming 3-D objects are visible. For example, if the 3-D object were a building, the backside of the building would not be visible. Thus, typical 3-D graphics systems include a visibility subsystem for determining which triangles are visible. Only those triangles that are found visible by the visibility subsystem are rendered, thus improving the efficiency of the computer graphics system.
Prior art methods of determining visibility of a triangle have included using distance information associated with the triangle or polygons. For example, if, at a particular pixel location, a current polygon is more distant than the last polygon drawn at that location, then the current polygon is not visible at that pixel location. Thus, in a z-buffer system, the distance to the last polygon for each pixel on the screen is stored in a z-buffer array. When determining whether a new polygon is visible, the depth value of each pixel of the polygon is compared to the corresponding element in the z-buffer array. If a pixel of the new polygon has a depth greater than the depth value in the corresponding z-buffer array element, then that pixel is not visible. Else, if a pixel of the new polygon has a depth less than the depth value in the corresponding z-buffer array element, then that pixel is visible, and its depth value is stored in the z-buffer array element.
The z-buffer technique requires depth comparisons on a per-pixel basis. Thus, the z-buffer technique requires expensive hardware to handle the required throughput. Additionally, many graphics systems now employ anti-aliasing techniques that generate several sub-pixels for each pixel displayed. Because each sub-pixel has a depth value, the z-buffer technique requires depth comparisons on a sub-pixel-by-sub-pixel basis, thus increasing costs even more.
Other techniques have tried to improve on the z-buffer method. For example, in a hierarchical z-buffer, the screen is partitioned into a hierarchy of regions, proceeding from a coarsest granularity to a finest granularity. The region at the top of a hierarchy may be a full screen, and the regions in the next level in the hierarchy may be the screen partitioned into quarters. These quarter screen regions are referred to as children of the full screen region, and the full screen regions is referred to as the ancestor of the quarter screen regions. Similarly, the hierarchy may continue down to a finest level in which each pixel or sub-pixel corresponds to a region. At each region of the hierarchical z-buffer, a maximum z value is maintained. The maximum z value of a region corresponds to the maximum z values of the region""s children. At the finest resolution, (i.e., at the pixel or sub-pixel level), the maximum z value corresponds to a traditional z-buffer. This methods attempts to determine visibility of a triangle at as high a level in the hierarchy as possible. For example, the minimum depth of a triangle may first be compared to the maximum z-value of the full screen region of the hierarchical z-buffer. If the minimum depth of the triangle is greater than the maximum z-value of the full screen region, then the triangle must be hidden. Therefore, the triangle need not be rendered. However, if the minimum depth of the triangle is not greater than the maximum z-value of the full screen region, then the triangle is similarly compared in each of the children of the full screen region. This process is similarly repeated down the hierarchy until the visibility of all the pixels in the triangle can be determined. If any pixel of any triangle is determined to be visible at the pixel or sub-pixel level, the maximum z values of the corresponding ancestor regions are updated with the new maximum z-value.
The hierarchical z-buffer method thus may be able to determine the visibility of a triangle without having to do a pixel-by-pixel comparison. However, the hierarchical z-buffer method is difficult to implement in hardware because of its iterative nature. For instance, z-values must be iteratively compared down the hierarchy, and maximum z-values must be iteratively updated up the hierarchy. Additionally, it is difficult to use the hierarchical z-buffer method when the depth compare operator changes in the course of displaying 3-D images, or when factors other than depth are to be used in determining visibility (i.e. stenciling).
The present invention offers methods and systems for determining visibility of groups of pixels in a 3-D graphics system. Broadly, according to the present invention, the visibility of a group of pixels is determined by comparing depth interval and coverage information of the group of pixels with depth interval and coverage information of a plurality of surfaces.
Benefits of the present invention include reducing the computation cost of visibility determination by determining visibility of groups of pixels without resorting to pixel-by-pixel depth computations and comparisons. Other benefits include providing an efficient method of determining visibility that may be easily implemented in hardware.
In one embodiment according to the invention, a method for determining visibility of groups of pixels performed by a computer graphics system is provided. The method comprises partitioning a display into a plurality of cells, wherein each of the plurality of cells includes a depth interval and a coverage for each of a plurality of surfaces having coverage within the each of the plurality of cells. The method additionally comprises receiving a depth interval and a coverage for a group of pixels having coverage within one or more of the plurality of cells. The method further comprises, for each of the one or more cells, determining a visibility of the group of pixels based on comparisons of the depth interval of the group of pixels with the depth intervals of the plurality of surfaces.
In another embodiment according to the invention, a visibility subsystem in a computer graphics system for determining visibility of groups of pixels is provided. The visibility subsystem includes a group depth buffer having a plurality of group depth buffer cells, each group depth buffer cell corresponding to a display region of a display. Each group depth buffer cell is configured to receive a depth interval of a group of pixels within the corresponding display region and a coverage of the group of pixels within the corresponding display region. Each group depth buffer cell is further configured to generate a visibility coverage of the group of pixels within the corresponding display region.
In yet another embodiment of the invention, a computer system for processing graphics data is provided. The computer system comprises a visibility subsystem coupled to a memory. The visibility subsystem includes a scan converter coupled to a group depth buffer, and the group depth buffer has a plurality of group depth buffer cells corresponding to a plurality of regions of a display. The visibility subsystem is configured to generate visibility coverages of groups of pixels. The computer system further comprises a rendering engine coupled to the visibility subsystem and the memory. The rendering engine is configured to receive visibility coverages of the groups of pixels and to render visible portions of the group of pixels.
In another aspect according to the invention, a method performed by a computer graphics system of determining a depth interval of a group of pixels within a region is provided. The method includes determining a depth of the group of pixels at a center of the region. The method also includes determining a bound on a positive change in depth of the group of pixels from the center of the region to any pixel of the group of pixels within the region, and determining a first endpoint of the depth interval based on the sum of the depth of the group of pixels at the center of the region with the bound on the positive change in depth. The method further includes determining a bound on a negative change in depth of the group of pixels from the center of the region to any pixel of the group of pixels within the region, and determining a second endpoint of the depth interval based on the subtraction of the bound on the negative change in depth from the depth of the group of pixels at the center of the region.
These and other features and advantages of the present invention will be better understood with reference to the detailed description below and the accompanying diagrams.